Large Number Arithmetic using Linked Lists

Due date: April 8^th , 2009

Integer data types limit us in terms of the range of numbers that can be used. They do not allow for numbers of great magnitude. If we wish to use numbers that go beyond the range of an integer data type, we would have to use software to do the arithmetic.

In this assignment, you would read an input file, which would list an operation, and then list two large numbers. Then, you would implement the operation on the two large numbers. ‘So easy’, you say? I don’t think so!

Here’s the tricky part. You would then have to represent each ‘big’ integer with a linked list, where each "node" in the list consists of a digit, the power of 10 to which it corresponds, and pointers to the next node. Thus, the number 8024070002 could be represented as :

(8·10⁹+2·10⁷+4·10⁶+7·10⁴+2·10⁰)

Your program would then have to be able to do the following:

1. It should be able to read an input file that would consist of an operation and two numbers on which the operation should be implemented. That is, the input data file will have an operator symbol on one line, followed by two numbers. Each number will begin on a separate line and may extend over several lines but will be terminated by a ;. Click here for a sample input file.

2. It should have a function that could create a linked list representation of the ‘big’ integer as the digits of the integer are read in from a data file. The integer may extend over multiple lines but will be terminated by a semicolon. No ‘0’ digits should be included in the list. The function should then return a pointer to the most significant digit of the list. This would be done twice for the two integers.

3. It should have a function that should be able to write to a file a large integer which has been stored as a linked list. The print should start on a new line, print 0 at appropriate points for missing powers, and have no more than 50 digits per line. One of the input parameter should be a pointer to the most significant digit of the linked list. This function will then be used to write the two integers, and the result to a file. Click here for a sample output file.

4. It should be able to add two large integers which have been stored as linked lists, returning a pointer to the most significant digit of the sum. If a 0 digit is created in the addition, it should NOT be stored in the list.

5. It should be able to print a report on the screen, that shows the values in the three queues, before it writes everything to a file, as stated in part (3). Click here to see the sample report on the screen.

The following items need to be submitted in an envelope

1. Stapled hardcopy, including:

· Coversheet -- including your name, the date, the course name, and the assignment number

· Pseudocode algorithm in the comments of the program code

· Source code

· Screenshots of test runs

2. Disk with only these items:

· Source code -- only your cpp and h files

· Executable files -- the exe file